package club.xiaojiawei.binarytree;

import java.util.LinkedList;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/14/22 5:55 PM
 * @question 100. 相同的树
 * @description 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 */
public class IsSameTree100 {

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
//        root1.right = new TreeNode(3);
        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
//        root2.right = new TreeNode(3);
        boolean result = isSameTree(root1, root2);
        System.out.println("是否相同："+result);
    }

    /**
     * BFS+两个队列
     * 时间复杂度：O(min(m,n))
     * @param p
     * @param q
     * @return
     */
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null){
            return q == null;
        }else if (q == null){
            return false;
        }else if (p.val != q.val){
            return false;
        }
        LinkedList<TreeNode> pQueue = new LinkedList<>();
        LinkedList<TreeNode> qQueue = new LinkedList<>();
        pQueue.add(p);
        qQueue.add(q);
        while (pQueue.size() > 0){
            TreeNode pCurrent = pQueue.pop();
            TreeNode qCurrent = qQueue.pop();
            if (pCurrent.left == null){
                if (qCurrent.left != null){
                    return false;
                }
            }else if (qCurrent.left == null){
                return false;
            }else if (pCurrent.left.val != qCurrent.left.val){
                return false;
            }else {
                pQueue.add(pCurrent.left);
                qQueue.add(qCurrent.left);
            }
            if (pCurrent.right == null){
                if (qCurrent.right != null){
                    return false;
                }
            }else if (qCurrent.right == null){
                return false;
            }else if (pCurrent.right.val != qCurrent.right.val){
                return false;
            }else {
                pQueue.add(pCurrent.right);
                qQueue.add(qCurrent.right);
            }

        }
        return true;
    }

    /**
     * 官方-DFS+递归
     * 时间复杂度：O(min(m,n))
     * @param p
     * @param q
     * @return
     */
    public static boolean isSameTree2(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree2(p.left, q.left) && isSameTree2(p.right, q.right);
        }
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
